Programmation
dynamique

Thème 5 — Partie B

NSI Terminale

Richard Bellman (1920—1984)

Mathématicien américain, il introduit la programmation dynamique au début des années 1950.

Le terme « programmation » signifiait alors planification, pas informatique.

Idée clé : résoudre un problème complexe en le décomposant en sous-problèmes, en stockant les résultats pour ne pas les recalculer.

La suite de Fibonacci

Définition :

F(0) = 0

F(1) = 1

F(n) = F(n-1) + F(n-2)

Les premiers termes : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…

Algorithme récursif naïf


def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Que se passe-t-il pour calculer fib(5) ?

Arbre des appels — `fib(5)`

Le problème : des calculs répétés !

fib(3) est calculé 2 fois
fib(2) est calculé 3 fois
fib(1) est calculé 5 fois

Pour fib(n), le nombre d'appels est de l'ordre de 2ⁿ

fib(40) → plus de 300 millions d'appels !

Complexité : O(2ⁿ) — exponentielle, donc inutilisable pour de grandes valeurs

Solution 1 : La mémoïsation

Principe : on garde en mémoire (dans un dictionnaire) les résultats déjà calculés.

Avant chaque calcul, on vérifie si le résultat est déjà connu → si oui, on le renvoie directement.

Cette approche est dite descendante (top-down) : on part du problème général et on descend vers les sous-problèmes.

Mémoïsation en Python


def fib_memo(n, cache={}):
    if n in cache:
        return cache[n]      # déjà calculé !
    if n <= 1:
        return n
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]

Résultat de la mémoïsation

Chaque valeur F(k) n'est calculée qu'une seule fois.

Nombre d'appels pour fib_memo(n) : n appels seulement.

Méthode	fib(30)	fib(40)	Complexité
Naïve	~1 s	~100 s	O(2ⁿ)
Mémoïsation	instantané	instantané	O(n)

Solution 2 : Approche ascendante

Principe : on calcule les petits sous-problèmes d'abord, puis on remonte jusqu'au résultat final.

On stocke les résultats dans un tableau.
Pas de récursivité !

Cette approche est dite ascendante (bottom-up).

Fibonacci bottom-up


def fib_dp(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Visualisation du tableau `dp`

Pour fib_dp(8) :

i	0	1	2	3	4	5	6	7	8
dp[i]	0	1	1	2	3	5	8	13	21

Optimisation espace : on n'a besoin que des deux dernières valeurs → O(1) en mémoire.

Récapitulatif Fibonacci

Approche	Récursion	Temps	Espace
Naïve	✔	O(2ⁿ)	O(n)
Mémoïsation	✔	O(n)	O(n)
Bottom-up (tableau)	✘	O(n)	O(n)
Bottom-up optimisé	✘	O(n)	O(1)

Quand utiliser la prog. dynamique ?

Un problème se prête à la programmation dynamique s'il vérifie deux propriétés :

Chevauchement de sous-problèmes
Les mêmes sous-problèmes sont résolus plusieurs fois.

Sous-structure optimale
La solution optimale du problème se construit à partir des solutions optimales de ses sous-problèmes.

Prog. dynamique vs Diviser pour régner

Diviser pour régner
(ex : tri fusion)

Sous-problèmes indépendants
Pas de recalcul inutile
Récursion simple

Prog. dynamique
(ex : Fibonacci)

Sous-problèmes qui se chevauchent
Stockage des résultats
Mémoïsation ou tableau

Application : Rendu de monnaie

Comment rendre la monnaie avec le minimum de pièces ?

L'algorithme glouton échoue

Pièces disponibles : 30, 24, 12, 6, 3, 1
Montant à rendre : 48

Glouton (prendre toujours la plus grande pièce) :
→ 30 + 12 + 6 = 3 pièces

Solution optimale :
→ 24 + 24 = 2 pièces ✔

Il faut une approche plus intelligente !

Relation de récurrence

dp[i] = nombre minimum de pièces pour rendre le montant i

Initialisation : dp[0] = 0

Récurrence :
Pour chaque pièce c disponible telle que c ≤ i :
dp[i] = min(dp[i], dp[i - c] + 1)

Exemple — pièces {1, 3, 4}, montant = 6

i	0	1	2	3	4	5	6
dp[i]	0	1	2	1	1	2	2

Pour rendre 6 : 3 + 3 ou 4 + 1 + 1 → minimum : 2 pièces

Code Python — Rendu de monnaie


def rendu_monnaie(montant, pieces):
    dp = [float('inf')] * (montant + 1)
    dp[0] = 0
    for i in range(1, montant + 1):
        for c in pieces:
            if c <= i and dp[i - c] + 1 < dp[i]:
                dp[i] = dp[i - c] + 1
    return dp[montant]

# Exemple
print(rendu_monnaie(48, [30, 24, 12, 6, 3, 1]))  # → 2

Ce qu'il faut retenir

La programmation dynamique résout les problèmes dont les sous-problèmes se chevauchent.

Deux approches : mémoïsation (top-down) ou tableau (bottom-up).

On passe d'une complexité exponentielle à une complexité polynomiale.

Applications classiques

Suite de Fibonacci ← fil rouge de ce cours
Rendu de monnaie (optimisation)
Plus grand carré de 1 dans une matrice
Distance d'édition (correcteur orthographique)
Problème du sac à dos (0/1 Knapsack)
Plus longue sous-séquence commune (LCS)
Algorithme de Bellman-Ford (chemins les plus courts)

Programmationdynamique